/* 
   Copyright 2012 Ryne Okimoto

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

/*
 * ICS 211
 * Fall 2011
 * Homework 5
 * @author Ryne Okimoto
 * 
 * LinkedList class.  Creates a linked list and performs
 * operations on that list.
 */

package dlldynamicset;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

// Old code implemented java.lang.iterable<E>

public class DLLDynamicSet <E, K extends Comparable<K>> implements java.lang.Iterable<E>
{	
	// Data for DLLDynamicSet
	private DLLNode<E, K> head;
	private DLLNode<E, K> tail;
	private int size;
	
	/**
	*	Default constructor
	*	Initializes an empty list.
	*/
	public DLLDynamicSet()
	{
		head = null;
		tail = null;
		size = 0;
	}
	
	private static class DLLNode<E, K extends Comparable<K>> implements Comparable<DLLNode<E, K>>{
		
		private E data;
		// Need to implement key
		private K key;
		private DLLNode<E, K> next;
		private DLLNode<E, K> previous;
		
		
		/**
		*	Constructor to create a node with a given datatype
		*/
		public DLLNode(E datavalue, K keyvalue){
			data = datavalue;
			// Initialize key
			key = keyvalue;
			next = null;
			previous = null;
		}
		
		public DLLNode
			(E datavalue, K keyvalue, DLLNode<E, K> nextNode, DLLNode<E, K> previousNode)
		{
			data = datavalue;
			// Initialize key
			key = keyvalue;
			next = nextNode;
			previous = previousNode;
		}
		
		public DLLNode<E, K> getNext()
		{
			return next;
		}
		
		public DLLNode<E, K> getPrevious()
		{
			return previous;
		}
		
		public void setNext(DLLNode<E, K> node)
		{
			next = node;
		}
		
		public void setPrevious(DLLNode<E, K> node)
		{
			previous = node;
		}
		
		public K getKey()
		{
			return key;
		}
		
		
		public E getData()
		{
			return data;
		}
		
		public String toString()
		{
			return key.toString();
		}
		
		public int compareTo(DLLNode<E, K> anotherRecord)
		{
			return this.key.compareTo(anotherRecord.getKey());
		}
	} // class DLLNode
	
	
	/**
	 * Class - SetIterator
	 * Description - Iterator for the superclass
	 * @author Ryne
	 *
	 */
	public class SetIterator implements java.util.Iterator<E>{
		
		private DLLNode<E, K> currentNode;
		
		private SetIterator(){
			currentNode = head;
		}
		
		public boolean hasNext(){
			return currentNode != null;
		}
		
		public E next(){
			if(hasNext()){
				E result = currentNode.getData();
			
				currentNode = currentNode.getNext();
				
				return result;
			}
			throw new NoSuchElementException();
		}
		
		public void remove(){
			throw new UnsupportedOperationException();
		}
	}
	
	public Iterator<E> iterator(){
		return new SetIterator();
	}
	
	/**
	 * Method - insertObject
	 * Description - Inserts an object and its key into the collection
	 * @param data
	 * @param key
	 * @return void
	 */
	public void insertObject(E data, K key){
		insert(new DLLNode<E, K>(data, key));
	}
	
	/**
	*	Method to insert an element into the list
	*	Pre: The list is sorted
	*	Post: The list is sorted
	*
	*/
	private void insert(DLLNode<E, K> nodeToAdd)
	{
		// Add to empty list
		if(head == null)
		{
			head = nodeToAdd;
			tail = nodeToAdd;
		}
		else
		{
			DLLNode<E, K> tempNode = head;
			while(tempNode.getNext() != null && nodeToAdd.compareTo(tempNode) > 0)
			{
				tempNode = tempNode.getNext();
			}
			
			// Add at front of list containing elements
			if(tempNode == head)
			{
				tempNode.setPrevious(nodeToAdd);
				nodeToAdd.setNext(tempNode);
				
				head = nodeToAdd;
			}
			
			// Add at end of list containing elements
			else if(tempNode == tail)
			{
				tempNode.setNext(nodeToAdd);
				nodeToAdd.setPrevious(tempNode);
				
				tail = nodeToAdd;
			}
			
			// Add to somewhere within the list
			else
			{
				// Connect added node
				nodeToAdd.setNext(tempNode);
				nodeToAdd.setPrevious(tempNode.getPrevious());
				
				// Change references for tempNode
				tempNode.getPrevious().setNext(nodeToAdd);
				tempNode.setPrevious(nodeToAdd);
			}
		} 
		
		size++;
	}
	
	/**
	 * Method - deleteKey
	 * Description - Searches the collection for a given key and deletes the first 
	 *               matching key.
	 * @param key
	 * @return boolean
	 */
	public boolean deleteKey(K key){
		boolean isDeleted = false;
		DLLNode<E, K> searchResult = search(key);
		
		if(searchResult != null){
			delete(searchResult);
			isDeleted = true;
		}
		
		return isDeleted;
	}
	
	/**
	*	Method to delete an element from the list if it exists
	*	Pre: The list is sorted
	*	Post: The list is sorted
	*/
	private void delete(DLLNode<E, K> nodeToDelete)
	{
		DLLNode<E, K> searchResult = null;
		
		if(head != null)
		{
			if(nodeToDelete.compareTo(head) == 0)
			{
				// Delete from list with one item
				if(head == tail)
				{
					head = null;
					tail = null;
				}
				// Delete from head of list
				else
				{
					head = head.getNext();
					head.setPrevious(null);
				}
			}
			// Delete from tail of list
			else if(nodeToDelete.compareTo(tail) == 0)
			{
				tail = tail.getPrevious();
				tail.setNext(null);
			}
			// Delete from within list
			else
			{
				searchResult = search(nodeToDelete.getKey());
				if(searchResult != null)
				{
					searchResult.getPrevious().setNext(searchResult.getNext());
					searchResult.getNext().setPrevious(searchResult.getPrevious());
				}
			}	
		}
	}
	
	public int size()
	{
		return size;
	}
	
	
	public boolean searchForKey(K key){
		if(search(key) ==  null){
			return false;
		}
		return true;
	}
	
	private DLLNode<E, K> search(K key)
	{
		DLLNode<E, K> searchResult = head;
		
		while((searchResult != null) && (searchResult.getKey().compareTo(key) != 0))
		{
			searchResult = searchResult.getNext();
		}
		
		return searchResult;
	}
	
	public DLLNode<E, K> minimum()
	{
		return head;
	}
	
	public DLLNode<E, K> maximum()
	{
		return tail;
	}
	
	public DLLNode<E, K> successor(DLLNode<E, K> node)
	{
		return node.getNext();
	}
	
	public DLLNode<E, K> predecessor(DLLNode<E, K> node)
	{
		return node.getPrevious();
	}
	
	public String toString()
	{
		DLLNode<E, K> printedNode = head;
		String printedString = null;
		
		while(printedNode != null)
		{
			if(printedString == null)
			{
				printedString = printedNode.toString() + "\n";
			}
			else
			{
				printedString = printedString.concat(printedNode.toString() + "\n");
			}
			
			printedNode = printedNode.getNext();
		}
		
		return printedString;
	}
	
	
	/**
	 * Unit tester for the class
	 * @param none
	 */
	public static void main(String[] args) 
	{
		
		char command = '0';
		DLLDynamicSet<String, String> testList = new DLLDynamicSet<String, String>();
		Scanner readInput = new Scanner(System.in);
		String key = null;
		String data = null;
		DLLNode<String, String> searchResult = null;
		
		readInput.useDelimiter("\n");
		
		System.out.println("Unit test for DLLDynamicSet and DLLNode\n");
		
		while(command != 'q')
		{
			System.out.print(
					"\n\n\n******   Command Menu   ******\n\n" +
					"1) Insert item\n" +
					"2) Delete item\n" +
					"3) Get size of list\n" +
					"4) Get minimum\n" +
					"5) Get maximum\n" +
					"6) Find successor\n" +
					"7) Find predecessor\n" +
					"8) Print keys\n" +
					"9) Read data from file\n" +
					"q) Quit\n\n" +
					": "
					);
			command = readInput.next().toCharArray()[0];
			
			switch(command)
			{
			case '1':
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test insert   ******" + "\n" +
						"Enter node data: "
						);
				data = readInput.next();
				
				System.out.print("Enter node key: ");
				key = readInput.next();
				
				testList.insert(new DLLNode<String, String>(data, key, null, null));
				
				break;
			case '2':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test delete   ******" + "\n" +
						"Enter key: "
						);
				key = readInput.next();
				
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					testList.delete(searchResult);
					System.out.println("Key deleted.");
				}
				else
				{
					System.out.println("Key not found.");
				}
				
				break;
			case '3':
				System.out.print("\n\n******   Size of list ******\n" +
						"Number of elements: " + testList.size()
						);
				break;
			case '4':
				System.out.print("\n\n******   Get minimum   ******\n" +
						"Minimum key: " + testList.minimum()
						);
				break;
			case '5':
				System.out.print("\n\n******   Get maximum   ******\n" +
						"Maximum key: " + testList.maximum()
						);
				break;
			case '6':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find successor   ******\n" +
						"Enter key: "
						);
				
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Successor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				
				break;
			case '7': 
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find predecessor   ******\n" +
						"Enter key: "
						);
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Predecessor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				break;
			case '8':
				System.out.println(testList);
				break;
			case '9':
				System.out.print("\n\n******   Read data from file   ******" + "\n" +
						"Enter a file name: "
						);
				//ReadStringFile fileToRead = new ReadStringFile(readInput.next());
				/*
				while(fileToRead.hasLine())
				{
					keyAndData = fileToRead.readLine();
					testList.insert(new DLLNode<String, String>(keyAndData, keyAndData));
				}
				*/
				break;
			case 'q':
				System.out.println("Exiting program...");
				break;
			default:
				System.out.println("Please choose a valid option.");
			}
			
		}
		
		
	}
}
